////////////////////////////////////////////////////////////////////////////////
//
//  The MIT License
//
//  Copyright (c) 2008 - 2010. Dimarik
//
//  Permission is hereby granted, free of charge, to any person obtaining a copy
//  of this software and associated documentation files (the "Software"), to deal
//  in the Software without restriction, including without limitation the rights
//  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//  copies of the Software, and to permit persons to whom the Software is
//  furnished to do so, subject to the following conditions:
//
//  The above copyright notice and this permission notice shall be included in
//  all copies or substantial portions of the Software.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//  THE SOFTWARE.
//
////////////////////////////////////////////////////////////////////////////////

package ru.goodcore.utils.gif
{

import __AS3__.vec.Vector;

import flash.geom.Rectangle;
import flash.utils.ByteArray;
import flash.utils.Endian;
import flash.utils.getTimer;
import flash.display.BitmapData;

// import flash.display.BitmapData;
/**
 *  @author				Dimarik
 *  @version			1.1
 *  @langversion		3.0
 *  @playerversion		9.0
 */
public class GIFDecoder 
{

	//-------------------------------------------------------------------------
	//
	//  Class methods
	//
	//-------------------------------------------------------------------------

	/**
	 * Performs the decode input GIF bytearray.
	 * 
	 * @param		input	The ByteArray to decode
	 * 
	 * @return				An array containing numbers of GIF bitmapdatas
	 * 
	 */
	public static function decode(input:ByteArray):Array { /* of BitmapData */
		var pos:uint = input.position;
		read(input);
		input.position = pos;

		return _frames;
	}

	//-------------------------------------------------------------------------
	//
	//  Class variables
	//
	//-------------------------------------------------------------------------

	/**
	 * @private
	 * 
	 * LZW dictionary size
	 */
	private static const DICTIONARY_SIZE:		uint = 1 << 12;

	//-------------------------------------------------------------------------
	//
	//  Private variables
	//
	//-------------------------------------------------------------------------

	/**
	 *  Storage for last graphic control extension disposal method.
	 */
	private static var _dispose:			uint= 0;

	/**
	 * Image width 
	 */
	private static var _width:				uint;

	/**
	 * Image height 
	 */
	private static var _height:				uint;

	/**
	 * Global color table
	 */
	private static var _globalColorTable:	Vector.<uint>;


	/**
	 * Background color
	 */
	private static var _bgColor:			uint;


	private static var _bmpd:				BitmapData;

	/**
	 * 0 = no action
	 * 1 = leave in place
	 * 2 = restore to bg
	 * 3 = restore to prev
	 */
	private static var _lastDispose:		uint = 0;

	/**
	 * Use transparent color
	 */ 
	private static var _transparency:		Boolean = false;

	/**
	 * Transparent color index
	 */
	private static var _transparencyIndex:	uint;

	/**
	 * Frames read from current file
	 */
	private static var _frames:				Array;

	/**
	 * Number of frames 
	 */
	//private static var _frameCount:			uint;

	//-------------------------------------------------------------------------
	//
	//  Private class methods
	//
	//-------------------------------------------------------------------------

	/**
	 * Reads GIF image from stream
	 *
	 * @param stream containing GIF file.
	 */
	private static function read(input:ByteArray):void {
		//_frameCount = 0;
		_frames = new Array();
		_globalColorTable = null;

		input.endian = Endian.LITTLE_ENDIAN;

		//-----------------------------
		// Header String[6]
		//-----------------------------

		/** signature & version [ignore] */
		input.position = 6;

		//-----------------------------
		// Logical Screen Descriptor
		//-----------------------------

		/** canvas width & height in pixels UI16 both */
		_width = input.readUnsignedShort();
		_height = input.readUnsignedShort();

		/** <Packed Fields> UI8 : */
		var byte:		uint = input.readUnsignedByte();

		/** bit 7    global color table flag           */
		/** bit 4-6  color resolution         [ignore] */
		/** bit 3    gct sort flag            [ignore] */
		/** bit 0-2  gct size                          */
		var gctSize:	uint = 2 << (byte & 0x07);

		/** background color index */
		var bgIndex:	uint = input.readUnsignedByte();

		/** pixel aspect ratio UI8 [ignore] */
		input.position += 1; 

		if ( (byte & 0x80) > 0 ) { // global color table flag raised
			_globalColorTable = readColorTable(gctSize, input);
			_bgColor = _globalColorTable[bgIndex];
		}

		//-----------------------------
		// GIF file content blocks
		//-----------------------------

		var run:	Boolean = true;
		var block:	ByteArray;

		while ( run ) {
			/** Extension Introducer */
			byte = input.readUnsignedByte();

			switch (byte) {

				/** Beginning of an extension block */
				case 0x21: {

					/** Extention Label */
					byte = input.readUnsignedByte();

					switch (byte) {

						/** Graphic Control Extension */
						case 0xF9: {
							readGraphicControlExtension(input);
							break;
						}

						/** Application Extension */
						//case 0xFF: {
						//	ignoreBlock(input);
							//if ( readApplicationExtension(input) == 'NETSCAPE2.0') {
								//readNetscapeExtension(input);
							//	ignoreBlock(input); // [ignore]
							//} else {
							//	ignoreBlock(input);
							//}
						//	break;
						//}


						/** Plain Text Label  */
						//case 0x01: {
						//	break;
						//}

						/** [ignore] */
						default: {
							ignoreBlock(input);
							break;
						}
					}
					break;
				}


				/** Image Separator */
				case 0x2C: {
					readImageDescriptor(input);
					break;
				}

				/** Terminator */
				case 0x3B: {
					run = false;
					break;
				}

				/** [ignore] */
				//case 0x00: {
				//	break;
				//}

			}
		}
	}


	//-------------------------------------------------------------------------
	//
	//   Extensions readers
	//
	//-------------------------------------------------------------------------

	/**
	 * @private
	 * 
	 * Reads Netscape extenstion to obtain iteration count [ignore]
	 * 
	 * @param input Input ByteArray
	 */
	private static function readNetscapeExtension(input:ByteArray):void {
		var block:		ByteArray = new ByteArray();
		var blockSize:	uint;

		while ( (blockSize = input.readUnsignedByte()) > 0) {
			block.length = 0;
			input.readBytes(block, 0, blockSize);
		}

	}

	/**
	 * @private
	 * 
	 * Reads Application Extension Block from input.
	 * 
	 * @param input Input ByteArray
	 * 
	 * @return Application Identifier & Application Authentication Code as string
	 */
	private static function readApplicationExtension(input:ByteArray):String {
		var blockSize:	uint = input.readUnsignedByte();
		var result:		String = input.readUTFBytes(blockSize);
		return result;
	}

	/**
	 * @private
	 * 
	 * Reads Graphics Control Extension values from input
	 * 
	 * @param input Input ByteArray
	 */
	private static function readGraphicControlExtension(input:ByteArray):void {
		/** Block Size [ignore] */
		input.readUnsignedByte();

		/** <Packed Fields> */
		var byte:uint = input.readUnsignedByte();
		
		/** bit 5-7 Reserved               [ignore] */
		/** bit 2-4 Disposal Method                 */
		/**
		 * 0 = no action
		 * 1 = leave in place
		 * 2 = restore to bg
		 * 3 = restore to prev
		 */
		_dispose = ((byte & 0x1c) >> 2) || 1;

		/** bit 1   User Input Flag        [ignore] */
		/** bit 0   Transparent Color Flag          */
		_transparency = (byte & 1) > 0;

		/** Delay Time before continuing (in 1/100 seconds) [ignore] */
		input.readUnsignedShort();

		/** Transparency Index */
		_transparencyIndex = input.readUnsignedByte();

		/** Block Terminator [ignore] */
		input.readUnsignedByte();
	}


	//-------------------------------------------------------------------------
	//
	//   Other
	//
	//-------------------------------------------------------------------------

	private static function readImageDescriptor(input:ByteArray):void {
		/** Image Left Position */
		var left:	uint = input.readUnsignedShort();
		/** Image Top Position  */
		var top:	uint = input.readUnsignedShort();
		/** Image Width */
		var width:	uint = input.readUnsignedShort();
		/** Image Image Height  */
		var height:	uint = input.readUnsignedShort();

		/** <Packed Fields>     */
		var byte:	uint = input.readUnsignedByte();

		/** bit 7   Local Color Table Flag             */
		var hasLCT:	Boolean = (byte & 0x80) > 0;

		/** bit 6   Interlace Flag           */
		var isInterlaced:	Boolean = (byte & 0x40) > 0;

		/** bit 5   Sort Flag                 [ignore] */
		/** bit 3,4 Reserved                  [ignore] */

		/** bit 0-2 Size of Local Color Table          */
		var lctSize:	uint = 2 << (byte & 0x07);

		if (hasLCT) {
			var activeColorTable:Vector.<uint> = readColorTable(lctSize, input);
		}
		else {
			activeColorTable = _globalColorTable;
		}

		var color:			uint = _transparency ? 0x00000000 : _bgColor;
		var bmpd:			BitmapData;

		switch (_lastDispose) {
			case 0:
				bmpd = new BitmapData( _width, _height, true, color);
				break;

			case 1:
				if (_bmpd) {
					bmpd = _bmpd.clone();
				} else {
					bmpd = new BitmapData( _width, _height, true, 0xFF000000);
				}
				break;

			case 2:
				bmpd = new BitmapData( _width, _height, true, color);
				break;

			case 3:
				bmpd = new BitmapData( _width, _height, true, color);
				break;
		}


		bmpd.lock();

var start:Number = getTimer();
		var outputBA:			ByteArray = new ByteArray();

		var NullCode:int = -1;
		var npix:int = width * height;
		var available:int;
		var clear:int;
		var code_mask:int;
		var code_size:int;
		var end_of_information:int;
		var in_code:int;
		var old_code:int;
		var bits:int;
		var code:int;
		var count:int;
		var i:int;
		var datum:int;
		var data_size:int;
		var first:int;
		var top1:int;
		var bi:int;
		var pi:int;

		var prefix:Vector.<uint> = new Vector.<uint> ( DICTIONARY_SIZE );
		var suffix:Vector.<uint> = new Vector.<uint> ( DICTIONARY_SIZE );
		var pixelStack:Vector.<uint> = new Vector.<uint> ( DICTIONARY_SIZE + 1 );

		//  Initialize GIF data stream decoder.
		
		var block:				ByteArray = new ByteArray();
		block.endian = Endian.LITTLE_ENDIAN;

		var buffer:uint = 0;
		
		data_size = input.readUnsignedByte();

		var tmpBlock:ByteArray;
		while ( (tmpBlock = readBlock(input)).length > 0) {
			tmpBlock.readBytes(block, block.length);
		}

		
		clear = 1 << data_size;
		end_of_information = clear + 1;
		available = clear + 2;
		old_code = NullCode;
		code_size = data_size + 1;
		code_mask = (1 << code_size) - 1;

		for (code = 0; code < clear; code++) {
			prefix[int(code)] = 0;
			suffix[int(code)] = code;
		}

		//  Decode GIF pixel stream.
		datum = bits = count = first = top1 = pi = bi = 0;

		while (true) {
			if (top1 == 0) {

				if (bits < code_size) {
					datum = block.readUnsignedShort();
					buffer = (datum << bits) | buffer;
					bits += 16;
				}
				//  Get the next code.
				code = buffer & code_mask;

				//  Interpret the code
				if (code == end_of_information)
					break;
				
				buffer >>= code_size;
				bits -= code_size;

				if (code == clear) {
					//  Reset decoder.
					code_size = data_size + 1;
					code_mask = (1 << code_size) - 1;
					available = clear + 2;
					old_code = NullCode;
					continue;
				}

				if (old_code == NullCode) {
					pixelStack[int(top1++)] = suffix[int(code)];
					old_code = code;
					first = code;
					continue;
				}

				in_code = code;

				if (code == available) {
					pixelStack[int(top1++)] = first;
					code = old_code;
				}

				while (code > clear) {
					pixelStack[int(top1++)] = suffix[int(code)];
					code = prefix[int(code)];
				}

				first = (suffix[int(code)]) & 0xff;

				//  Add a new string to the string table,
				if (available >= DICTIONARY_SIZE) break;
				pixelStack[int(top1++)] = first;
				prefix[int(available)] = old_code;
				suffix[int(available)] = first;
				available++;

				if (
					((available & code_mask) == 0) &&
					available < DICTIONARY_SIZE
				) {
					code_size++;
					code_mask += available;
				}
				old_code = in_code;
			}

			//  Pop a pixel off the pixel stack.
			top1--;
			//pixels[int(pi++)] = pixelStack[int(top1)];
			outputBA.writeUnsignedInt(  activeColorTable[ pixelStack[int(top1)] ]);
		}

/*
		for (i = pi; i < npix; i++) {
			pixels[int(i)] = 0; // clear missing pixels
		}
*/
trace('decoding: ', (getTimer() - start));

start = getTimer();
		outputBA.position = 0;
		bmpd.setPixels(new Rectangle(left, top, width, height), outputBA);
		bmpd.unlock();

trace('copy: ', (getTimer() - start));
		_frames.push(bmpd);
		_bmpd = bmpd;
		_lastDispose = _dispose;
	}

	/**
	 * @private
	 * 
	 * Reads and store next image.
	 * 
	 * @param input Input bytearray
	 */
	private static function readImageDescriptor1(input:ByteArray):void {
		/** Image Left Position */
		var left:	uint = input.readUnsignedShort();
		/** Image Top Position  */
		var top:	uint = input.readUnsignedShort();
		/** Image Width */
		var width:	uint = input.readUnsignedShort();
		/** Image Image Height  */
		var height:	uint = input.readUnsignedShort();

		/** <Packed Fields>     */
		var byte:	uint = input.readUnsignedByte();

		/** bit 7   Local Color Table Flag             */
		var hasLCT:	Boolean = (byte & 0x80) > 0;

		/** bit 6   Interlace Flag           */
		var isInterlaced:	Boolean = (byte & 0x40) > 0;

		/** bit 5   Sort Flag                 [ignore] */
		/** bit 3,4 Reserved                  [ignore] */

		/** bit 0-2 Size of Local Color Table          */
		var lctSize:	uint = 2 << (byte & 0x07);

		if (hasLCT) {
			var activeColorTable:Vector.<uint> = readColorTable(lctSize, input);
		}
		else {
			activeColorTable = _globalColorTable;
		}

		var color:			uint = _transparency ? 0x00000000 : _bgColor;
		var bmpd:			BitmapData;

		switch (_lastDispose) {
			case 0:
				bmpd = new BitmapData( _width, _height, true, color);
				break;

			case 1:
				if (_bmpd) {
					bmpd = _bmpd.clone();
				} else {
					bmpd = new BitmapData( _width, _height, true, 0xFF000000);
				}
				break;

			case 2:
				bmpd = new BitmapData( _width, _height, true, color);
				break;

			case 3:
				bmpd = new BitmapData( _width, _height, true, color);
				break;
		}

		bmpd.lock();

		var outputBA:			ByteArray = new ByteArray();

		var minSymbolSize:		uint = input.readUnsignedByte();
		var symbolSize:			uint = minSymbolSize + 1;
		var symbolMask:			uint = (1 << symbolSize) - 1;

		var $CC:				uint = 1 << minSymbolSize; // Clear Code symbol definition
		var $EOI:				uint = $CC + 1;

		var dictionary:			Vector.<ByteArray> = new Vector.<ByteArray>( DICTIONARY_SIZE );
		var dictionaryPosition:	uint = $CC + 2;

		var vectorTmp:			ByteArray;

		for (i = 0; i < $CC; i++) { // Init dictionary
			vectorTmp = new ByteArray();
			vectorTmp.writeShort(i);
			dictionary[i] = vectorTmp;
		}

		var block:				ByteArray = new ByteArray();
		block.endian = Endian.LITTLE_ENDIAN;
		var hasBits:			uint = 0;

		var tmpBlock:ByteArray;
		while ( (tmpBlock = readBlock(input)).length > 0) {
			tmpBlock.readBytes(block, block.length);
		}
		
		//block.position = block.length - 2;
		

		block.length = block.length + (block.length % 2);

		var buffer:	uint = 0;

		//trace(traceByteArray(block));
var start:Number = getTimer();
		while (true) {

			if (hasBits < symbolSize) {
				byte = block.readUnsignedShort();
				buffer = (byte << hasBits) | buffer;
				hasBits += 16;
			}

			var symbol:uint = buffer & symbolMask;

			if (symbol == $EOI)
				break;

			buffer >>= symbolSize;
			hasBits -= symbolSize;

			// The symbol is first uncompressed symbol just after clear procedure
			if ( oldSymbol == $CC ) {
				var oldSymbol:uint = symbol;
				outputBA.writeUnsignedInt( activeColorTable[ symbol ] );
				continue;
			}

			if (symbol == $CC) { // Reset decoder
				symbolSize = minSymbolSize + 1;
				symbolMask = (1 << symbolSize) - 1;
				dictionaryPosition = $CC + 2;
				oldSymbol = symbol;
				continue;
			}

			var vectorOld:	ByteArray = ByteArray(dictionary[oldSymbol]);

			var i:			uint = 0;
			var len:		uint = vectorOld.length;

			vectorTmp = new ByteArray();

			if (symbol < dictionaryPosition) {
				vectorTmp.writeBytes(vectorOld, 0, len);

				var vector:	ByteArray = ByteArray(dictionary[symbol]);

				vectorTmp.writeBytes(vector, 0, 2);

				len = vector.length >> 1;
				i = 0;
				vector.position = 0;

				while ( i < len ) {
					outputBA.writeUnsignedInt( activeColorTable[ vector.readUnsignedShort() ] );
					i++;
				}

			} else {
				len >>= 1;
				vectorOld.position = 0;

				while ( i < len ) {
					outputBA.writeUnsignedInt( activeColorTable[ vectorOld.readUnsignedShort() ] );
					i++;
				}

				vectorOld.position = 0;
				outputBA.writeUnsignedInt( activeColorTable[ vectorOld.readUnsignedShort() ] );

				vectorTmp.writeBytes(vectorOld);
				vectorTmp.writeBytes(vectorOld, 0, 2);
			}

			dictionary[dictionaryPosition++] = vectorTmp;
			oldSymbol = symbol;

			if ( dictionaryPosition > symbolMask && dictionaryPosition < DICTIONARY_SIZE ) {
				symbolSize++;
				symbolMask |= dictionaryPosition;
			}

		}
trace('decoding: ', (getTimer() - start));

start = getTimer();
		outputBA.position = 0;
		bmpd.setPixels(new Rectangle(left, top, width, height), outputBA);
		bmpd.unlock();

trace('copy: ', (getTimer() - start));
		_frames.push(bmpd);
		_bmpd = bmpd;
		_lastDispose = _dispose;
	}

	/**
	 * Reads next variable length block from input.
	 *
	 * @return ByteArray contains block bytes
	 */
	private static function readBlock(ba:ByteArray):ByteArray {
		var blockSize:	uint = ba.readUnsignedByte();
		var result:		ByteArray = new ByteArray();

		if (blockSize > 0)
			ba.readBytes(result, 0, blockSize);

		return result;
	}

	/**
	 * Reads color table as ARGB 32bit integer values
	 *
	 * @param numColors 	Number of colors to read
	 * @param ba		 	Source bytearray
	 * 
	 * @return Vector.<uint> containing ARGB 32bit colors
	 */
	private static function readColorTable(numColors:uint, ba:ByteArray):Vector.<uint> {
		var numBytes:	uint = 3 * numColors;
		var position:	uint = ba.position + numBytes;
		var i:			uint = 0;
		var result:		Vector.<uint> = new Vector.<uint>(numColors);
		result.fixed = true;

		ba.position = position--;

		while (numColors--) {
			result[numColors] = 0xFF000000 |
								(ba[position--] & 0xFF) |
								((ba[position--] & 0xFF) << 8) |
								((ba[position--] & 0xFF) << 16);
		}

		return result;
	}

	/**
	 * Skips variable length blocks up to and including
	 * next zero length block.
	 */
	private static function ignoreBlock(ba:ByteArray):void {
		var subblock:		ByteArray;
		while ( (subblock = readBlock(ba)).length > 0 ) void;
	}

}
}